package seqList.LeetCode;

import org.w3c.dom.ls.LSException;

import java.util.List;

/*
LeetCode 第83题。
链表的反转   三种方法
 */
public class Num206 {
    // 方法三  递归：
    public ListNode reverseList(ListNode head){
          //如果是空或者只有头节点，返回
        if(head == null || head.next == null){
            return head;
        }
        ListNode sec = head.next;
        //反转之后的链表
        ListNode newHead = reverseList(head.next);
          // 让后面的节点指向前面的节点
        sec.next = head;
        head.next = null;
        return newHead;
    }

    // 方法二  迭代方法：
//    public ListNode reverseList(ListNode head){
//    //如果是空或者只有头节点，返回
//        if (head == null || head.next == null){
//            return head;
//        }
//        ListNode prev = null;
//        ListNode cur = head;
//        while (cur != null ){
//            ListNode next = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = next;
//        }
//        return prev;
//
//    }

    // 方法一，遍历链表的同时，创建一个新的链表
//    public ListNode reverseList(ListNode head) {
//        //如果是空或者只有头节点，返回
//        if(head == null || head.next == null){
//            return head;
//        }
//        ListNode DummyHead = new ListNode(5001);
//        //至少有两个节点
//        while (head != null) {
//            ListNode node = new ListNode(head.val);
//            node.next = DummyHead.next;
//            DummyHead.next = node;
//            head = head.next;
//        }
//        return DummyHead.next;
//    }


}
